#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Jun  5 21:29:55 2022

@author: liqingsimac
"""

def sieve_v1(n):
    ''' Use Sieve of Eratosethenes to compute list of primes 
        less than or equal to n. Version 1
    '''
    primes = list(range(2,n+1))
    for p in primes:
#        print('primes=',primes)
#        print('p=',p)
        if p*p>n:
            break
        product = 2*p
#        print('product=',product)
        while product <=n:
            if product in primes:
                primes.remove(product)
#                print('primes=',primes)
            product+=p
#            print('product=',product)
    return len(primes), primes

def sieve_v2(n):
    ''' Sieve of Eratosethenes to compute list of primes
        less than or equal to n. Version 2
    '''
    sieve = [True]*(n+1)
    print('sieve=',sieve)
    for i in range(3,n+1,2):
        print('i=',i)
        if i*i>n:
            break
        if sieve[i]:
            print('sieve[i]=',sieve[i])
            print('sieve[i*i::2*i]=',sieve[i*i::2*i])
            sieve[i*i::2*i]=[False]*((n-i*i)//(2*i)+1)
            print('sieve=',sieve)
    answer = [2]+[i for i in range(3,n+1,2) if sieve[i]]
    return len(answer),answer


# =============================================================================
# from sieves import sieve_v1,sieve_v2
# sieve_v1?
# sieve_v1(18)
# sieve_v2(18)
# timeit(sieve_v1(1000))
# timeit(sieve_v2(1000))
# 
# =============================================================================
